package 力扣.字符串;

public class 最长公共前缀14 {
    public static void main(String[] args) {
//        String[] strings = new String[]{"flower","flow","flight","floo"};
//        String[] strings = new String[]{"flower"};
//        String[] strings = new String[]{""};
//        String[] strings = new String[]{};
//        String[] strings = new String[]{"fl","flow"};
//        String[] strings = new String[]{"","flow"};
//        String[] strings = new String[]{"a","aca","accb","b"};
//        String[] strings = new String[]{"reflower","flow","flight"};
        String[] strings = new String[]{"ab","a"};
        String s = longestCommonPrefix2(strings);
        System.out.println(s);
    }

    /**
     * 横向扫描：遍历字符串，每两个相邻的字符进行比较，得到相同字符的长度（临近字符长度）。而当前临近字符长度只能 小于或者等于 上一个临近字符长度
     */
    public static String longestCommonPrefix(String[] strs) {
        int len = strs.length;
        if (len == 0) {
            return "";
        }
        int re = strs[0].length();
        int te = 0;
        for (int i = 1; i < len; i++) {//遍历字符串
            String s1 = strs[i];
            String s2 = strs[i - 1];
            for (int j = 0; j < s1.length(); j++) {
                if (j < s2.length()) { //两个字符串可能长度不一样，这里需要进行判断
                    char c1 = s1.charAt(j);
                    char c2 = s2.charAt(j);
                    if (c1 == c2) {//字符相同则 te++
                        te++;
                    } else {//否则，退出循环
                        break;
                    }
                } else {
                    break;
                }
            }
            // re记录上一个公共前缀的长度 te记录当前公共前缀的长度
            if (te <= re) {// te必须小于等于re  才能将te赋值给re  否则re还是其本身
                re = te;
            }
            te = 0;//te重新赋值为0
        }
            String st = strs[0].substring(0, re);//截取字符串
            return st;
    }

    /**
     * 纵向扫描 使用索引 i 扫描每一个字符串的第 i 个字符，若存在不相同的字符，则循环停止。
     */
    public static String longestCommonPrefix2(String[] strs) {
        int length = strs.length;
        if (length == 0) {
            return "";
        }
        int re = 0;
        int te = 0;//作为扫描到非公共字符的哨兵
        for (int i = 0; i < strs[0].length(); i++) {// i 作为每个字符索引
            for (int j = 0; j < length - 1; j++) {//j 作为每个字符串索引
                if ( (strs[j].length() - 1) < i || (strs[j+1].length() - 1 < i) ){
                    te++;
                    break;
                }
                char c1 = strs[j].charAt(i);
                char c2 = strs[j+1].charAt(i);
                if (c1 != c2) {//一旦不相等
                    te++;// 哨兵变化
                    break;
                }
            }
            if (te == 0){//哨兵不变则记录长度，接着进入下一个索引
                re++;
            }else {//若哨兵改变则说明当前索引i对应的字符不相等
                break;//退出
            }
        }
        return strs[0].substring(0,re);
    }
}
